Á¤º¸°úÇÐȸ ÄÄÇ»ÆÃÀÇ ½ÇÁ¦ ³í¹®Áö (KIISE Transactions on Computing Practices)
Current Result Document :
ÇѱÛÁ¦¸ñ(Korean Title) |
µð½ºÅ© ±â¹Ý ±×·¡ÇÁ ¿£ÁøÀÇ ÀÔÃâ·Â ¼º´É Çâ»óÀ» À§ÇÑ ±×·¡ÇÁ ¿À´õ¸µ |
¿µ¹®Á¦¸ñ(English Title) |
Improving the I/O Performance of Disk-Based Graph Engine by Graph Ordering |
ÀúÀÚ(Author) |
ÀÓ±ÙÇÐ
±èÁ¤Çö
ÀÌÀºÀç
¼Áö¿ø
Keunhak Lim
Junghyun Kim
Eunjae Lee
Jiwon Seo
|
¿ø¹®¼ö·Ïó(Citation) |
VOL 24 NO. 01 PP. 0040 ~ 0045 (2018. 01) |
Çѱ۳»¿ë (Korean Abstract) |
ºòµ¥ÀÌÅÍ¿Í ¼Ò¼È ³×Æ®¿öÅ©ÀÇ ¹ßÀü°ú ´õºÒ¾î °Å´ëÇÑ ±×·¡ÇÁ¸¦ ó¸®ÇÏ´Â ¿¬±¸µµ È°¹ßÇÏ°Ô ÁøÇàµÇ°í ÀÖ´Ù. ÃÖ±Ù ±×·¡ÇÁ ó¸®ÀÇ ¼º´É Çâ»óÀ» À§ÇØ Gorder ¶ó´Â ±×·¡ÇÁ ¿À´õ¸µ ±â¹ýÀÌ Á¦¾ÈµÇ¾ú´Ù. ÀÌ ±â¹ýÀº ¸Þ¸ð¸® »óÀÇ ±×·¡ÇÁ ·¹À̾ƿôÀ» º¯ÇüÇÏ¿© µ¥ÀÌÅÍ Á¢±Ù ÆÐÅÏÀ» CPU ij½Ã¿¡ ÀûÇÕÇÏ°Ô ¹Ù²ÞÀ¸·Î½á ¼º´ÉÀ» Çâ»ó½ÃŲ´Ù. ÇÏÁö¸¸ ±×·¡ÇÁ ¾Ë°í¸®ÁòÀÇ Ä³½Ã Áö¿ª¼º¿¡¸¸ ÃÊÁ¡À» µÎ°í ¼³°èµÇ¾ú±â ¶§¹®¿¡ µð½ºÅ© ±â¹Ý ±×·¡ÇÁ ¿£Áø¿¡¼´Â ÀûÇÕÇÏÁö ¾Ê°í Àüó¸® ºñ¿ëµµ Å©´Ù´Â ¹®Á¦Á¡ÀÌ ÀÖ´Ù. Á¦½ÃÇÑ ¹®Á¦Á¡À» ÇØ°áÇϱâ À§ÇØ, º» ³í¹®¿¡¼´Â »õ·Î¿î ±×·¡ÇÁ ¿À´õ¸µÀÎ I/O Order¸¦ Á¦¾ÈÇÏ¿´´Ù. I/O Order´Â µð½ºÅ© ±â¹ÝÀÇ ±×·¡ÇÁ ¿£Áø¿¡¼ Áö¿ª¼º ¿Ü¿¡ ÀÔÃâ·Â ºÎÇϸ¦ °í·ÁÇÏ¿© ¼³°èµÇ¾ú´Ù. ¶ÇÇÑ, ¿À´õ¸µ ºñ¿ëÀ» ÁÙÀ̱â À§ÇØ °£´ÜÇÑ schemeÀ» »ç¿ëÇÑ´Ù. º» ³í¹®¿¡¼ Á¦½ÃµÈ I/O Order´Â Gorder¿Í ºñ±³ÇØ Àüó¸® ºñ¿ëÀÌ ÃÖ´ë 9.6¹è °¨¼ÒÇÏ¿´°í ¼º´ÉÀº Áö¿ª¼ºÀÌ ³·Àº ±×·¡ÇÁ ¾Ë°í¸®Áò¿¡¼ Random ´ëºñ ÃÖ´ë 2¹è ÀÌ»ó Çâ»óµÇ¾ú´Ù.
|
¿µ¹®³»¿ë (English Abstract) |
With the advent of big data and social networks, large-scale graph processing becomes popular research topic. Recently, an optimization technique called Gorder has been proposed to improve the performance of in-memory graph processing. This technique improves performance by optimizing the graph layout on memory to have better cache locality. However, since it is designed for in-memory graph processing systems, the technique is not suitable for disk-based graph engines; also the cost for applying the technique is significantly high. To solve the problem, we propose a new graph ordering called I/O Order. I/O Order considers the characteristics of I/O accesses for SSDs and HDDs to improve the performance of disk-based graph engine. In addition, the algorithmic complexity of I/O Order is simple compared to Gorder, hence it is cheaper to apply I/O Ordering. I/O order reduces the cost of pre-processing up to 9.6 times compared to that of Gorder¡¯s, still its performance is 2 times higher compared to the Random in low-locality graph algorithms.
|
Å°¿öµå(Keyword) |
±×·¡ÇÁ ó¸®
±×·¡ÇÁ ¿£Áø
±×·¡ÇÁ ¿À´õ¸µ
ÀÔÃâ·Â ¸ðµ¨¸µ
graph processing
graph engine
graph ordering
I/O cost modeling
|
ÆÄÀÏ÷ºÎ |
PDF ´Ù¿î·Îµå
|